package ljl.codetop300;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.SortedMap;
import java.util.SortedSet;
import java.util.TreeMap;
import java.util.TreeSet;

public class _295_median_finder {

  static class test {
    class MedianFinder {

      PriorityQueue<Integer> bigHead = new PriorityQueue<>(Comparator.reverseOrder());
      PriorityQueue<Integer> smallHead = new PriorityQueue<>();

      /**
       * 这是官方题解，速度比路飞的快 10ms 多
       */
      public void addNum(int num) {
        if (smallHead.isEmpty() || smallHead.peek() <= num) {
          smallHead.offer(num);
          if (smallHead.size() - 1 > bigHead.size())
            bigHead.offer(smallHead.poll());
        } else {
          bigHead.offer(num);
          if (bigHead.size() > smallHead.size())
            smallHead.offer(bigHead.poll());
        }
      }

      public void addNum2(int num) {
        if (bigHead.size() == smallHead.size()) {
          bigHead.offer(num);
          smallHead.offer(bigHead.poll());
        } else {
          smallHead.offer(num);
          bigHead.offer(smallHead.poll());
        }
      }

      public double findMedian() {
        if (bigHead.size() < smallHead.size()) return smallHead.peek();
        return (bigHead.peek() + smallHead.peek()) / 2.0;
      }
    }
  }

  /**
   * 诡异解法
   * 不但不好理解，效率还低
   * 效率低就算了，我还看了半天
   * 血亏
   */
  static class MedianFinder {
    TreeMap<Integer, Integer> nums;
    int n;
    int[] left;
    int[] right;

    public MedianFinder() {
      nums = new TreeMap<>();
      n = 0;
      left = new int[2];
      right = new int[2];
    }

    public void addNum(int num) {
      nums.put(num, nums.getOrDefault(num, 0) + 1);
      if (n == 0) {
        left[0] = right[0] = num;
        left[1] = right[1] = 1;
      } else if ((n & 1) != 0) {
        // left == right，比 left 小，所以直接 left-- 就行了
        if (num < left[0]) {
          decrease(left);
        } else {
          increase(right);
        }
      } else {
        if (num > left[0] && num < right[0]) {
          increase(left);
          decrease(right);
        }
        else if (num >= right[0]) {
          increase(left);
        } else {
          decrease(right);
          System.arraycopy(right, 0, left, 0, 2);
        }
      }
      n++;
    }

    public double findMedian() {
      return (left[0] + right[0]) / 2.0;
    }

    /**
     * 谁能解释一下， [1] 怎么变成 1 了？
     */
    private void increase(int[] iterator) {
      iterator[1]++;
      if (iterator[1] > nums.get(iterator[0])) {
        iterator[0] = nums.ceilingKey(iterator[0] + 1);
        iterator[1] = 1;
      }
    }

    private void decrease(int[] iterator) {
      iterator[1]--;
      if (iterator[1] == 0) {
        iterator[0] = nums.floorKey(iterator[0] - 1);
        iterator[1] = nums.get(iterator[0]);
      }
    }
  }

  static class copy_off {
    static class MedianFinder {
      static class Node {
        int val;
        int count;
        Node(int val, int count) {
          this.val = val; this.count = count;
        }
      }
      Node left, right;
      TreeMap<Integer, Integer> sorted = new TreeMap<>();
      int n = 0;

      public void addNum(int num) {
        sorted.put(num, sorted.getOrDefault(num, 0) + 1);
        if (n == 0) {
          left = new Node(num, 1);
          right = new Node(num, 1);
          sorted.put(num, 1);
        } else if (n % 2 == 1) {
          if (left.val > num) {
            dec(left);
          } else {
            inc(right);
          }
        } else {
          if (left.val < num && right.val > num) {
            inc(left);
            dec(right);
          } else if (left.val >= num) {
            dec(right);
            left.val = right.val;
            left.count = right.count;
          } else {
            inc(left);
          }
        }
        n++;
      }
      public double findMedian() {
        return (left.val + right.val) / 2.;
      }
      void inc(Node node) {
        if (++node.count > sorted.get(node.val)) {
          node.val = sorted.ceilingKey(node.val + 1);
          node.count = 1;
        }
      }
      void dec(Node node) {
        if (--node.count == 0) {
          node.val = sorted.floorKey(node.val - 1);
          node.count =sorted.get(node.val);
        }
      }
    }
  }

}
